#include <iostream>
#include <climits>
#include <vector>
#include <set>
#include <math.h>
#include <LEDA/numbers/fp.h>
#include <LEDA/graphics/graphwin.h>
#include <LEDA/graphics/color.h>
#include <LEDA/core/p_queue.h>
#include <LEDA/core/stack.h>
#include <LEDA/core/tuple.h>
#include "control.h"

using namespace leda;



// Gets minimal color for given node v in graph g and coloring
int get_minimal_color(graph &g , GraphWin &gw ,  node_array<int> coloring , node &v) {
	std::set<int> used; // set of used colors
	int freeCounter = 0;

	gw.message("Looking at all neighbor colors to get the optimal color for the current node.");

	node u;
	edge e;
	forall_inout_edges(e, v) {

		gw.set_color(e , blue);
		gw.set_width(e, 2);

		u = g.opposite(e , v);

		//std::cout << coloring[u] << std::endl;
		//do not take color of node u for v.
		if (coloring[u] != -1)
			used.insert(coloring[u]);

		//show, that this node was looked at.
		gw.set_border_width(u , 4);
		control_wait(0.75);

		gw.set_border_width(u , 0);

		gw.set_color(e , grey3);
		gw.set_width(e, 1);

	}

	gw.del_messages();

	//Find first unused color (if number of colors would be bound we could just use an array,
	// but since we do not have a bound, we have to use this.)

	//This should be O(log n) where n is the current number of colors (amortized)
	//Code from stackoverflow (http://stackoverflow.com/questions/980377/find-the-lowest-unused-number)
	std::set<int>::iterator iter = used.lower_bound(freeCounter);
	while (iter != used.end() && *iter == freeCounter) {
	   ++iter;
	   ++freeCounter;
	}
	return freeCounter++;

}

// We don not know yet if in- or decreasing, so we hide this in a method to be changed easily
int get_key(int degree) {
	return -degree; //decreasing
	//return degree; //increasing
}

// Computes a greedy coloring for the graph g and displays it using gw.
void greedyColoring(graph &g, GraphWin &gw) {

	leda_color color_map[8];
	color_map[0] = green;
	color_map[1] = red;
	color_map[2] = yellow;
	color_map[3] = orange;
	color_map[4] = cyan;
	color_map[5] = pink;
	color_map[6] = brown;
	color_map[7] = green2;

	//storage for color of nodes
	node_array<int> coloring(g,-1);

	//Priority queue for nodes, sorted by degree of nodes in it
	p_queue<double , node> pq;

	node v;
	forall_nodes(v , g) {
		//add node v to priority queue
		pq.insert(get_key(g.degree(v)) , v);
	}

	int number_of_colors = 0;

	int pos = 1;
	//Take nodes from priority queue until all nodes have a color = until no more nodes in pq
	while (!pq.empty()) {
		gw.message("Taking next node from queue.");

		p_queue<int , node>::pq_item p = pq.find_min();

		v = pq.inf(p);
		pq.del_min();

		gw.set_user_label(v , string("Pos.: %i" , pos));

		// Mark node v as currently active
		gw.set_border_width(v, 3);
		control_wait(2);

		//Get minimal color
		int color = get_minimal_color(g , gw , coloring ,  v);
		coloring[v] = color;
		// update the number of colors if necessary
		if (color+1 > number_of_colors)
			number_of_colors = color +1;

		//wait a second before coloring the node (to look at neighbors, etc.)
		control_wait(1);


		//Color node with fixed color (start from beginning if too many colors!
		gw.set_color(v , color_map[color % coloring.size()]);

		//Display Position in queue and number of color (in case there are not enough colors)
		gw.set_user_label(v , string("Pos.: %i \nColor: %i" , pos , color));

		//reset border of current node since it is done.
		gw.set_border_width(v , 0);

		control_wait(1);

		//increase position in ordering for next round.
		pos++;
	}

	gw.message(string( "Done. %i  colors were used" , number_of_colors));

}


int main(int argc, char *argv[]) {

    GraphWin gw(800, 600);
    gw.display();
    create_control();
    gw.set_directed(false);
    if (argc > 1)
        gw.read(argv[1]);
    gw.edit();
    graph &g = gw.get_graph();
    if (g.number_of_nodes() == 0) {
        gw.close(); destroy_control();
        exit(1);
    }

    //color all edges and nodes grey
    edge e;
    forall_edges(e, g){
    	node v = g.target(e);
    	node s = g.source(e);

     	gw.set_width(e, 1);

        gw.set_color(e, grey3);
        gw.set_color(v , grey3);
        gw.set_color(s , grey3);

        gw.set_label_type(v, user_label);
        gw.set_label_type(s, user_label);

        gw.set_border_color(v , blue);
        gw.set_border_color(s , blue);

        gw.set_border_width(v , 0);
        gw.set_border_width(s , 0);

    }

    // Make nodes rectangluar so we can read the labels inside.
    gw.set_node_shape(rectangle_node);
    gw.set_node_width(60);


    greedyColoring(g , gw);


    gw.acknowledge("Ready!");
    gw.edit();
    gw.close();
    destroy_control();
    exit(0);
}
